package cm.unit3.theme4;

import cm.commom.ListNode;

import java.util.ArrayList;
import java.util.List;

public class FindKthToTail {

    public ListNode FindKthToTail (ListNode pHead, int k){
        if (pHead==null || k==0){
            return null;
        }

        ListNode cursor = pHead;
        int cnt = 0;
        // 先走k步
        while (++cnt < k){
            if (cursor.next==null){
                return null;
            }
            cursor = cursor.next;
        }

        ListNode target = pHead;
        while (cursor.next!=null){
            target = target.next;
            cursor = cursor.next;
        }
        return target;
    }

    public ListNode FindKthToTail02 (ListNode pHead, int k) {
        // write code here
        if(pHead == null){
            return null;
        }
        // 借助数组存储；也可使用双指针
        List<ListNode> list = new ArrayList();
        int length = 0;
        for(ListNode node = pHead;node!=null;node = node.next){
            list.add(node);
            length++;
        }
        if(k > length || k == 0){
            return null;
        }
        return list.get(length-k);
    }
}
